The anti-forcing number of a perfect matching $M$ of a graph $G$ is theminimal number of edges not in $M$ whose removal to make $M$ as a uniqueperfect matching of the resulting graph. The set of anti-forcing numbers of allperfect matchings of $G$ is the anti-forcing spectrum of $G$. In this paper, wecharacterize the plane elementary bipartite graph whose minimum anti-forcingnumber is one. We show that the maximum anti-forcing number of a graph is atmost its cyclomatic number. In particular, we characterize the graphs with themaximum anti-forcing number achieving the upper bound, such extremal graphs area class of plane bipartite graphs. Finally, we determine the anti-forcingspectrum of an even polygonal chain in linear time.
展开▼
机译:图$ G $的完美匹配$ M $的反强制数是不在$ M $中的边的最小数量,将其去除以使$ M $作为结果图的唯一完美匹配。完全匹配的$ G $的反强制数集是$ G $的反强制范围。本文对最小反作用力数为一的平面基本二部图进行了刻画。我们表明图的最大反强迫数最多是其圈数。特别地,我们用最大抗力数达到上限的特征来刻画图,这是平面二部图的极值图区域类别。最后,我们确定线性时间内均匀多边形链的反强迫谱。
展开▼